﻿#define _CRT_SECURE_NO_WARNINGS
#pragma warning(disable:6031)
//#define size 5
//#include<stdio.h>
//int main()
//{
//	//char c[5] = { 'a','b','c','\0' };
//	//printf("%s\n", c);
//	/*char a[10] = { '5' };*/
//	char str[size] = { 0 };
//	printf("%d\n", sizeof(str));
//	char num['0'];//该数组的大小是 该字符对应的ASCII码值
//	printf("%d\n", sizeof(num));
//	return 0;
//}


//编写一个函数，计算字符串中含有的不同字符的个数。字符在 ASCII 码范围内(0~127 ，包括 0 和 127)，换行表示结束符，不算在字符里。不在范围内的不作统计。多个相同的字符只计算一次
//例如，对于字符串 abaca 而言，有 a、b、c 三种不同的字符，因此输出 3 。
//
//数据范围： 1 \le n \le 500 \1≤n≤500
//输入描述：
//输入一行没有空格的字符串。
//
//输出描述：
//输出 输入字符串 中范围在(0~127，包括0和127)字符的种数。

//没有空格的字符串 说明可以用scanf 来读取
//#include<stdio.h>
//#include<string.h>
//int main()
//{
//	char str[501] = { 0 };
//	gets(str);
//	int len = strlen(str);
//	int i = 0;
//	int count = 1;
//	for (i = 1; i < len; i++)
//	{
//		if (str[i] >= 0 && str[i] <= 127)
//		{
//			int j = 0;
//			for ( j = 0; j < i; j++)
//			{
//				if (str[i] == str[j])
//				{
//					break;
//				}
//			}
//			if (j == i)
//			{
//				count++;
//			}
//		}
//	}
//	printf("%d\n", count);
//	return 0;
//}


//
//给定一个大小为 n 的数组，找到其中的多数元素。多数元素是指在数组中出现次数 大于 ⌊ n / 2 ⌋ 的元素。
//
//你可以假设数组是非空的，并且给定的数组总是存在多数元素
//#include<stdio.h>
//int cmp(void* a, void* b)
//{
//	return *(int*)a - *(int*)b;
//}
//int majorityElement(int* nums, int numsSize) {
//	qsort(nums, numsSize, sizeof(int), cmp);
//	int i = 0;
//	int j = 0;
//	int count = 1;
//	int major = nums[0];
//	////先把数组排序
//	//for (i = 0; i < numsSize; i++)
//	//{
//	//	for (j = 0; j < numsSize - 1 - i; j++)
//	//	{
//	//		if (nums[j] > nums[j + 1])
//	//		{
//	//			int tem = nums[j];
//	//			nums[j] = nums[j + 1];
//	//			nums[j + 1] = tem;//大的排在后面
//	//		}
//	//	}
//	//}
//	
//	//这里使用冒泡排序会超时 所以我们选择快速排序
//	
//	//排序完成 就可以遍历了
//	for (i = 0; i < numsSize; i++)
//	{
//		if (nums[i] == nums[i + 1])
//		{
//			count++;
//			if (count > (numsSize / 2))
//			{
//				major = nums[i];
//				break;
//			}
//				
//		}
//		else if(nums[i]<nums[i+1])
//		{
//			count = 1;
//		}
//	}
//	return major;
//}
// 
// //暴力解法 但是时间复杂度太高！！！
// //直接枚举每一个元素 再加遍历
//#include<stdio.h>
//int majorityElement(int* nums, int numsSize) {
//	int i = 0;
//	int j = 0;
//	int major = nums[0];
//	for (i = 0; i < numsSize; i++)
//	{
//		int count = 0;
//		for (j = 0; j < numsSize; j++)
//		{
//			if (nums[j] == nums[i])
//			{
//				count++;
//			}
//			if (count > (numsSize / 2))
//			{
//				major = nums[j];
//			}
//		}
//	}
//	return major;
//}
int main()
{
	int nums[9] = { 2,2,1,1,1,2,2,1,1 };
	int numsSize=sizeof(nums)/sizeof(nums[0]);
	printf("%d\n", majorityElement(nums, numsSize));
	return 0;
}